Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

  1. X X X X
  2. X O O X
  3. X X O X
  4. X O X X

After running your function, the board should be:

  1. X X X X
  2. X X X X
  3. X X X X
  4. X O X X

Solution:

  1. public class Solution {
  2.   int[] dx = {-1, 1, 0, 0};
  3.   int[] dy = {0, 0, -1, 1};
  5.   public void solve(char[][] board) {
  6.     if (board == null || board.length == 0 || board[0].length == 0) return;
  8.     int n = board.length;
  9.     int m = board[0].length;
  11.     // scan the borders and mark the 'O's to '1'
  12.     for (int i = 0; i < n; i++)
  13.       for (int j = 0; j < m; j++)
  14.         if ((i == 0 || i == n - 1 || j == 0 || j == m - 1) && board[i][j] == 'O')
  15.           bfs(board, n, m, i, j);
  17.     // scan the inner area and mark the 'O's to 'X'
  18.     for (int i = 1; i < n; i++)
  19.       for (int j = 1; j < m; j++)
  20.         if (board[i][j] == 'O')
  21.           board[i][j] = 'X';
  23.     // reset all the '1's to 'O's
  24.     for (int i = 0; i < n; i++)
  25.       for (int j = 0; j < m; j++)
  26.         if (board[i][j] == '1')
  27.           board[i][j] = 'O';
  29.   }
  31.   void bfs(char[][] board, int n, int m, int i, int j) {
  32.     Queue<int[]> queue = new LinkedList<int[]>();
  33.     queue.add(new int[]{i, j});
  35.     board[i][j] = '1';
  37.     while (!queue.isEmpty()) {
  38.       int[] pos = queue.poll();
  40.       for (int k = 0; k < 4; k++) {
  41.         i = pos[0] + dx[k];
  42.         j = pos[1] + dy[k];
  44.         if (i >= 0 && i < n && j >= 0 && j < m && board[i][j] == 'O') {
  45.           board[i][j] = '1';
  46.           queue.add(new int[]{i, j});
  47.         }
  48.       }
  49.     }
  50.   }
  51. }